package LinkedList;

import Node.ListNode;

public class ReverseList {

    /**
     * 迭代式翻转单链表
     * @param head 链表头结点
     * @return 翻转后的链表头结点
     */
    public ListNode iterationReverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        // 由于单链表的结构，至少需要三个指针才能完成迭代翻转
        ListNode pre, cur, next;
        // cur 是当前遍历的节点，next 是当前节点的下一个节点，pre 是当前节点的前一个节点
        pre = null;
        cur = head;
        next = head.next;
        while (cur != null) {
            // 逐个节点翻转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = next;
            if (next != null) {
                next = next.next;
            }
        }

        // 返回翻转后的链表头结点
        return pre;
    }

    /**
     * 递归式翻转单链表
     * @param head 链表头结点
     * @return 翻转后的链表头结点
     */
    public ListNode recursiveReverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode last = recursiveReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}
